/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class LongestPalindromicSubstring {

	/**
	 Given a string S, find the longest palindromic substring in S.
	 You may assume that the maximum length of S is 1000, 
	 and there exists one unique longest palindromic substring.
	 
	 http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
	 */
	public String longestPalindrome(String s) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (s == null || s.isEmpty()) {
			return null;
		}
		// this is WRONG solution
		return longestCommonConsecutiveSequence(s, new StringBuilder(s)
				.reverse().toString());
	}

	/* #1 solution (WRONG) longest common consecutive sequence of the string and it's reversed string.
	Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.
	Let’s try another example:
		S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
		The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.
	*/
	public String longestCommonConsecutiveSequence(String s1, String s2) {
		if (s2.length() < s1.length()) {
			String tmp = s1;
			s1 = s2;
			s2 = tmp;
		}
		String[] dp = new String[s2.length() + 1];
		for (int i = 0; i < dp.length; i++) {
			dp[i] = "";
		}

		String result = "";
		for (int i1 = 0; i1 < s1.length(); ++i1) {
			for (int i2 = s2.length() - 1; i2 >= 0; --i2) {
				if (s1.charAt(i1) == s2.charAt(i2)) {
					dp[i2 + 1] = dp[i2] + s1.charAt(i1);
				} else {
					dp[i2 + 1] = "";
				}
				result = result.length() < dp[i2 + 1].length() ? dp[i2 + 1]
						: result;
			}
		}

		return result;
	}

	// #2 brute force to check all subset to find palindrome string

	/* #3 DP time O^2, space O^2
	To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes. Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.
	Base case P[i, i] = ture
	          P[i, i+1] = Si == Si+1
	 		  P[i,j] = P[i+1, j-1] and Si == Sj
	
	 */
	public String longestPalindromeDP(String s) {
		if (s.isEmpty())
			return s;
		int length = s.length();
		int start = 0;
		int maxLength = 1;
		boolean[][] dp = new boolean[length][length];
		for (int i = length - 1; i >= 0; i--) {
			for (int j = i; j < length; j++) {
				if (s.charAt(i) == s.charAt(j)
						&& (j - i <= 2 || dp[i + 1][j - 1])) {
					dp[i][j] = true;
					if (j - i + 1 > maxLength) {
						start = i;
						maxLength = j - i + 1;
					}
				}
			}
		}

		return s.substring(start, start + maxLength);
	}

	/* #4 space O^2
	 */
	public String longestPalindromeN2(String s) {
		if (s.isEmpty())
			return s;
		int length = s.length();
		String result = s.substring(0, 1);
		for (int i = 1; i < length; i++) {
			String str = expandPalindrome(s, i, i);
			result = result.length() < str.length() ? str : result;

			str = expandPalindrome(s, i - 1, i);
			result = result.length() < str.length() ? str : result;
		}

		return result;
	}

	private String expandPalindrome(String s, int left, int right) {
		while (left >= 0 && right < s.length()
				&& s.charAt(left) == s.charAt(right)) {
			left--;
			right++;
		}

		return s.substring(left + 1, right);
	}

	/**
	 * 
	 */
	public LongestPalindromicSubstring() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LongestPalindromicSubstring lps = new LongestPalindromicSubstring();
		String s1 = "FABABCDV";
		String s2 = "DEABABCDH";
		String result = lps.longestCommonConsecutiveSequence(s1, s2);
		System.out.printf("Result is : %s (6)", result);
	}

}
